翻訳と辞書
Words near each other
・ "O" Is for Outlaw
・ "O"-Jung.Ban.Hap.
・ "Ode-to-Napoleon" hexachord
・ "Oh Yeah!" Live
・ "Our Contemporary" regional art exhibition (Leningrad, 1975)
・ "P" Is for Peril
・ "Pimpernel" Smith
・ "Polish death camp" controversy
・ "Pro knigi" ("About books")
・ "Prosopa" Greek Television Awards
・ "Pussy Cats" Starring the Walkmen
・ "Q" Is for Quarry
・ "R" Is for Ricochet
・ "R" The King (2016 film)
・ "Rags" Ragland
・ ! (album)
・ ! (disambiguation)
・ !!
・ !!!
・ !!! (album)
・ !!Destroy-Oh-Boy!!
・ !Action Pact!
・ !Arriba! La Pachanga
・ !Hero
・ !Hero (album)
・ !Kung language
・ !Oka Tokat
・ !PAUS3
・ !T.O.O.H.!
・ !Women Art Revolution


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Lucas–Lehmer test : ウィキペディア英語版
Lucas primality test

In computational number theory, the Lucas test is a primality test for a natural number ''n''; it requires that the prime factors of ''n'' − 1 be already known. It is the basis of the Pratt certificate that gives a concise verification that ''n'' is prime.
==Concepts==
Let ''n'' be a positive integer. If there exists an integer 1 < ''a'' < ''n'' such that
:a^\ \equiv\ 1 \pmod n \,
and for every prime factor ''q'' of ''n'' − 1
:a^\ \not\equiv\ 1 \pmod n \,
then ''n'' is prime. If no such number ''a'' exists, then ''n'' is either 1 or composite.
The reason for the correctness of this claim is as follows: if the first equivalence holds for ''a'', we can deduce that ''a'' and ''n'' are coprime. If ''a'' also survives the second step, then the order of ''a'' in the group (Z/''n''Z)
* is equal to ''n''−1, which means that the order of that group is ''n''−1 (because the order of every element of a group divides the order of the group), implying that ''n'' is prime. Conversely, if ''n'' is prime, then there exists a primitive root modulo ''n'', or generator of the group (Z/''n''Z)
*. Such a generator has order |(Z/''n''Z)
*| = ''n''−1 and both equivalences will hold for any such primitive root.
Note that if there exists an ''a'' < ''n'' such that the first equivalence fails, ''a'' is called a Fermat witness for the compositeness of ''n''.

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Lucas primality test」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.